/*!
优先队列，小顶堆
leetcode 官方提供的方法

用法：
const minPriorityQueue = new MinPriorityQueue() // 构造
minPriorityQueue.enqueue('value', 1) // 入队，两个参数 element, priority 后者用于排序
minPriorityQueue.front() // {element: 'value', priority: 1} 返回 priority 最小项
minPriorityQueue.dequeue() // {element: 'value', priority: 1} 出列并返回 priority 最小项
minPriorityQueue.isEmpty() // true 是否为空

*/
export default class MinPriorityQueue {
  constructor() {
    this.heap = []
  }
  swap(i, j) {
    const tmp = this.heap[i]
    this.heap[i] = this.heap[j]
    this.heap[j] = tmp
  }
  getParentIndex(index) {
    return (index - 1) >> 1
  }
  shiftUp(index) {
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] && this.heap[parentIndex].priority > this.heap[index].priority) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }
  getLeftIndex(index) {
    return (index << 1) + 1
  }
  getRightIndex(index) {
    return (index << 1) + 2
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] && this.heap[leftIndex].priority < this.heap[index].priority) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] && this.heap[rightIndex].priority < this.heap[index].priority) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  enqueue(element, priority) {
    this.heap.push({ element, priority })
    this.shiftUp(this.heap.length - 1)
  }
  front() {
    return this.heap[0]
  }
  dequeue() {
    const tmp = this.heap[0]
    if (this.heap.length === 1) this.heap.pop()
    else {
      this.heap[0] = this.heap.pop()
      this.shiftDown(0)
    }
    return tmp
  }
  isEmpty() {
    return this.heap.length === 0
  }
}
